#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <set>
using namespace std;

template <class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<string>            // 走偏特化为string
{
	size_t operator()(const string& key)  // 将string转化为size_t
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

////////////////////////////////////////////////////////////

namespace hash_bucket
{
	template <class T>
	struct HashNode
	{
		HashNode(const T data)
			:_data(data)
			, _next(nullptr)
		{
		}
		T _data;
		HashNode<T>* _next;
	};

	// 前置声明,不需要写缺省参数
	template <class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template <class K, class T,class Ref, class Ptr, class KeyOfT, class Hash>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht; 
		size_t _hashi;

		__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			:_node(node)
			, _pht(pht)
			, _hashi(hashi)
		{
		}

		__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			:_node(node)
			, _pht(pht)
			, _hashi(hashi)
		{
		}

		Self& operator++()      // 前置++
		{

			if (_node->_next)
			{
				// 如果当前桶的节点下一个不为空，那么就走到下一个节点
				_node = _node->_next;
			}
			else
			{
				// 如果当前桶为空了，就走到下一个桶去
				++_hashi;
				while (_hashi < _pht->_tables.size())          // _pht中的tables是私有的，所以需要加友元
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}
					++_hashi;
				}

				if (_hashi == _pht->_tables.size())  // 如果走到头了，那么就是没找到下一个桶
				{
					_node = nullptr;
				}
			}
			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

	};

	// unordered_set -> HashTable<K, K>
	// unordered_map -> HashTable<K, pair<K, V>>
	template <class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		typedef HashNode<T> Node;
		// 声明友元
		template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct __HTIterator;

	public:
		typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;

		iterator begin()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this, i);
				}
			}
			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this, -1);
		}
		// const迭代器
		const_iterator begin() const
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this, i);
				}
			}
			return end();
		}

		const_iterator end() const 
		{
			return const_iterator(nullptr, this, -1);
		}

		HashTable()
		{
			_tables.resize(10);
		}



		pair<iterator, bool> Insert(const T& data)
		{
			Hash hf;
			KeyOfT kot;

			iterator it = Find(kot(data));
			if (it != end())
				return make_pair(it, false);


			if (_n == _tables.size())         // 如果负载因子到了1了，就进行扩容，传统写法
			{
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)       // 将节点一个一个拿下来，找新表的重新映射的位置插入
					{
						Node* next = cur->_next;
						size_t hashi = hf(kot(cur->_data)) % newTables.size();

						cur->_next = newTables[i];
						newTables[i] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}

			size_t hashi = hf(kot(data)) % _tables.size();   // 算出是那个桶
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return make_pair(iterator(newnode, this, hashi), true);
		}

		iterator Find(const K& key)
		{
			Hash hf;
			KeyOfT kot;

			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];

			while (cur)
			{
				if (kot(cur->_data) == key)
					return iterator(cur, this, hashi);
				cur = cur->_next;

			}

			return end();
		}

		bool Erase(const K& key)
		{
			Hash hf;
			KeyOfT kot;

			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;

			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)     // 如果前一个为空，说明是头删
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

		void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;             // 单桶的最大长度
			size_t sum = 0;
			double averageBucketLen = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
					bucketSize++;
				size_t bucketLen = 0;
				while (cur)
				{
					bucketLen++;
					cur = cur->_next;
				}

				sum += bucketLen;
				if (bucketLen > maxBucketLen)
					maxBucketLen = bucketLen;
			}
			averageBucketLen = (double)sum / (double)bucketSize;

			cout << "桶的个数：" << bucketSize << endl;
			cout << "最大桶的长度：" << maxBucketLen << endl;
			printf("平均桶的长度：%lf\n", averageBucketLen);
		}

		~HashTable()    // 存在的是vector的list，所以需要我们自己手动释放
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}

		}

	private:
		vector<Node*> _tables;
		int _n = 0;
	};
}


